import random
import time
import numpy as np

def quicksort(arr):
    """
    快速排序算法实现
    """
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准值
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

def generate_test_data(size=10000, range_min=0, range_max=10000):
    """
    生成测试数据
    """
    return [random.randint(range_min, range_max) for _ in range(size)]

def test_quicksort():
    """
    测试快速排序算法
    """
    print("===== 快速排序测试 =====")
    
    # 生成测试数据
    test_data = generate_test_data(10000, 0, 10000)
    print(f"生成测试数据，大小: {len(test_data)}")
    
    # 测试原始数据是否正确
    print(f"原始数据前10个元素: {test_data[:10]}")
    
    # 测量排序前的运行时间
    start_time = time.time()
    
    # 进行排序
    sorted_data = quicksort(test_data.copy())
    
    # 计算运行时间
    elapsed_time = time.time() - start_time
    print(f"排序完成，运行时间: {elapsed_time:.6f} 秒")
    
    # 验证排序结果
    assert np.all(sorted_data[:-1] <= sorted_data[1:]), "排序结果不正确"
    print("排序结果正确验证通过")
    
    # 测试排序结果的前10个和后10个元素
    print(f"排序后的前10个元素: {sorted_data[:10]}")
    print(f"排序后的后10个元素: {sorted_data[-10:]}")

if __name__ == "__main__":
    test_quicksort()